#include"tree.h"
#include"Queue.h"
void PreSort(BTNode* root) {
	if (root == NULL) {
		return NULL;
	}
	printf("%d ", root->val);
	PreSort(root->left);
	PreSort(root->right);
}
void InSort(BTNode* root) {
	if (root == NULL) {
		return NULL;
	}
	InSort(root->left);
	printf("%d ", root->val);
	InSort(root->right);
}
void BackSort(BTNode* root) {
	if (root == NULL) {
		return NULL;
	}
	BackSort(root->left);
	BackSort(root->right);
	printf("%d ", root->val);
}
int BinaryTreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0; 
	}
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->right)+ BinaryTreeLeafSize(root->left);
}
int BinaryTreeLevelSize(BTNode* root,int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
int BinaryTreeDepth(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int leftD = BinaryTreeDepth(root->left);
	int rightD = BinaryTreeDepth(root->right);
	return leftD > rightD ? leftD + 1 : rightD + 1;
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == x) {
		return root;
	}
	BTNode* leftNdoe = BinaryTreeFind(root->left, x);
	if (leftNdoe) {
		return leftNdoe;
	}
	BTNode* rightNode = BinaryTreeFind(root->right, x);
	if (rightNode) {
		return rightNode;
	}
	return NULL;
}
void BinaryTreeDestroy(BTNode** root) {
	if (*root == NULL) {
		return NULL;
	}
	BinaryTreeDestroy(&(*root)->left);
	BinaryTreeDestroy(&(*root)->right);
	free(*root);
	*root = NULL;
}
void leverOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty) {
		BTNode* front = QueueFront(&q);
		printf("%d ", front->val);
		QueuePop(&q);
		if (root->left) {
			QueuePush(&q, root->left);
		}
		if (root->right) {
			QueuePush(&q, root->right);
		}
	}
	QueueDestroy(&q);
}
bool BinaryTreeComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (root == NULL) {
			break;
		}
		QueuePush(&q, root->left);
		QueuePush(&q, root->right);
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (root != NULL) {
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}